package com.myown.structure;

/**
 * 散列表 <p>
 *
 * @author lincky
 * @version v1.0.0
 * @time 2017.02.24 14:33
 */
public class HashTable<K, V> {

    /**
     * 默认容量
     */
    private static final int DEFAULT_CAPACITY = 16;

    /**
     * 散列表容量
     */
    private int capacity;
    /**
     * 节点大小
     */
    private int size;

    /**
     * 散列表
     */
    private Node<K, V>[] table;

    public HashTable() {
        this(DEFAULT_CAPACITY);
    }

    public HashTable(int capacity) {
        assert capacity >= 0;
        // 保证容量是2的次方
        int temp = 1;
        while (temp < capacity) {
            temp <<= 2;
        }
        this.capacity = temp;
        table = new Node[this.capacity];
    }

    /**
     * 添加键值对 <p>
     *
     * @param key 键
     * @param value 值
     */
    public void put(K key, V value) {
        checkKey(key);
        int position = hash(key);
        Node<K, V> node = table[position];
        while (node != null) {
            // 相同键采取覆盖方式
            if (node.key.equals(key)) {
                node.value = value;
                return;
            }
            node = node.next;
        }
        Node<K, V> newNode = new Node<>(key, value);
        if (table[position] != null) {
            newNode.next = table[position];
        }
        table[position] = newNode;
        size++;
    }

    /**
     * 移除键值对 <p>
     *
     * @param key 键
     */
    public void remove(K key) {
        checkKey(key);
        int position = hash(key);
        Node<K, V> node = table[position];
        if (node == null) {
            return;
        }
        if (node.key.equals(key)) {
            table[position] = node.next;
            size--;
            return;
        }
        while (node.next != null) {
            if (node.next.key.equals(key)) {
                node.next = node.next.next;
                size--;
                return;
            }
            node = node.next;
        }
    }

    /**
     * 查找键值对 <p>
     *
     * @param key 键
     */
    public V get(K key) {
        checkKey(key);
        int position = hash(key);
        Node<K, V> node = table[position];
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    /**
     * 查找节点 <p>
     *
     * @param key 键
     */
    public Node<K, V> getNode(K key) {
        checkKey(key);
        int position = hash(key);
        Node<K, V> node = table[position];
        while (node != null) {
            if (node.key.equals(key)) {
                return node;
            }
            node = node.next;
        }
        return null;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 哈希算法 <p>
     *
     * @param key 键
     * @return 哈希码
     */
    private int hash(K key) {
        return key == null ? 0 :
                key.hashCode() % capacity;
    }

    static class Node<K ,V> {
        private final K key;
        private V value;
        private Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 键保证不为空
     * @param key 键
     */
    private final void checkKey(K key) {
        // TODO: 2017/2/24 keyNullException
        assert key != null;
    }

    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer();
        buffer.append("{");

        for (int i = 0; i < capacity; i++) {
            Node<K, V> node = table[i];
            while (node != null) {
                buffer.append(node.key + ":" + node.value + ", ");
                node = node.next;
            }
        }

        if (buffer.length() > 1) {
            buffer.delete(buffer.length() - 2, buffer.length());
        }

        buffer.append("}");

        return buffer.toString();
    }

}
